#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end()); // 排序
        vector<vector<int>> ret;        // 存结果
        int len = nums.size();
        for (int a = 0; a < len - 3;)
        {
            for (int b = a + 1; b < len - 2;)
            {
                long long for_num = (long long)target - nums[a] - nums[b];
                int c = b + 1, d = len - 1;
                while (c < d)
                {
                    if (nums[c] + nums[d] > for_num)
                    {
                        d--;
                    }
                    else if (nums[c] + nums[d] < for_num)
                    {
                        c++;
                    }
                    else
                    {
                        ret.push_back({ nums[a],nums[b],nums[c],nums[d] });
                        d--;
                        c++;
                        while (nums[c] == nums[c - 1] && c < d)
                        {
                            c++;
                        }
                        while (nums[d] == nums[d + 1] && c < d)
                        {
                            d--;
                        }
                    }
                }
                b++;
                while (nums[b] == nums[b - 1] && b < len - 2)
                {
                    b++;
                }
            }
            a++;
            while (nums[a] == nums[a - 1] && a < len - 3)
            {
                a++;
            }
        }
        return ret;
    }

};

class Solution {
public:
    int triangleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int ret = 0;
        int len = nums.size();
        if (len < 3)
        {
            return 0;
        }
        for (int c = len - 1; c > 1; c--)
        {
            int a = 0, b = c - 1;
            while (a < b)
            {
                if (nums[a] + nums[b] > nums[c])
                {
                    ret += (b - a);
                    b--;
                }
                else
                {
                    a++;
                }
            }
        }
        return ret;
    }
};